package com.ting.test.algorithms.大厂刷题班;

import com.ting.test.algorithms.排序算法.插入排序1;

/**
 * 给定一个字符串数组，求所有字符串的最长公共前缀
 * 利用前缀树的思路
 */

public class 求一个字符数组的最长公共前缀解法2 {
    public static void main(String[] args) {
        String[] arr = new String[]{"dsdaf", "dsfa", "dsfsad", "dsfa"};
        String str = process(arr);
        System.out.println(str);
    }

    private static String process(String[] arr) {
        TrieTree root = new TrieTree();

        for (int i = 0; i < arr.length; i++) {
            root.add(arr[i]);
        }
        int index = root.getCommonPrex(arr[0], arr.length);

        return arr[0].substring(0, index-1);
    }

    public static class TrieTree {
        private char base = 'a';
        private Node root = new Node();


        public void add(String str) {
            root.pass = root.pass + 1;
            Node cur = root;
            final char[] chars = str.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                int index = chars[j] - base;
                Node node = cur.nexts[index];
                if (node == null) {
                    node = new Node();
                }
                node.pass = node.pass + 1;
                if (j == chars.length - 1) {
                    node.end = node.end + 1;
                }
            }
        }

        public int getCommonPrex(String str, int length) {
            final char[] chars = str.toCharArray();

            Node cur = root;
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - base;
                final Node next = cur.nexts[index];
                if (next == null) {
                    return index;
                }
                if (next.pass != length) {
                    return index;
                }
            }
            return 0;

        }

    }

    public static class Node {
        int pass;//表示通过该节点的个数
        int end;//表示以该节点结尾的个数
        Node[] nexts = new Node[26];

        public Node(int pass, int end, Node[] nexts) {
            this.pass = pass;
            this.end = end;
            this.nexts = nexts;
        }

        public Node() {

        }

    }

}
